#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    bool isValid(string s)
    {
        stack<char> st;
        for (auto e : s)
        {
            if (e == '(' || e == '{' || e == '[')
            {
                st.push(e);
            }
            else
            {
                if (st.empty())
                {
                    return false;
                }
                char tmp = st.top();
                if (e == ')' && tmp != '(' ||
                    e == '}' && tmp != '{' ||
                    e == ']' && tmp != '[')
                {
                    return false;
                }
                st.pop();
            }
        }
        return st.empty();
    }
};